// Package medium
// url: https://leetcode.cn/problems/is-subsequence/description/
package simple

func isSubsequence(s string, t string) bool {

	if len(s) == 0 {
		return true
	}
	if len(s) > len(t) {
		return false
	}

	indexS, indexT := 0, 0
	for indexS < len(s) && indexT < len(t) {
		for indexT < len(t) && s[indexS] != t[indexT] {
			indexT++
		}
		if indexS < len(s) && indexT < len(t) && s[indexS] == t[indexT] {
			indexS++
			indexT++
		}
	}

	if indexS < len(s) && indexT == len(t) {
		return false
	}

	return indexS == len(s)
}

func isSubsequenceOptimize(s string, t string) bool {

	i, j := 0, 0
	for i < len(s) && j < len(t) {
		if s[i] == t[j] {
			i++
		}
		j++
	}

	return i == len(s)
}
